/**
 * @(#)数数字.java, 9月 11, 2023.
 * <p>
 * Copyright 2023 yuanfudao.com. All rights reserved.
 * FENBI.COM PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package yfd;

/**
 * @author leiwenkang
 */
public class ChatNumber {
    public static void main(String[] args) {
        int waysOf4 = countWays(4);
        System.out.println("n = 4 时的可能性：" + waysOf4);

        int waysOf10 = countWays(10);
        System.out.println("n = 10 时的可能性：" + waysOf10);

        int winningWaysOf4 = countWinningWays(4, true);
        System.out.println("n = 4 时先手获胜的可能性：" + winningWaysOf4);

        int winningWaysOf10 = countWinningWays(10, true);
        System.out.println("n = 10 时先手获胜的可能性：" + winningWaysOf10);
    }
    /**
     * 第一问，相当于斐波拉契数列
     * @return
     */
    public static int countWays(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        int first = 1;
        int second = 2;

        int result = 0;
        for (int i = 2; i < n; i++) {
            result = first + second;
            first = second;
            second = result;
        }

        return result;
    }

    /**
     * 第二问，计算先手获胜的可能性
     * 相对较难
     * @param n
     * @param isFirst
     * @return
     */
    public static int countWinningWays(int n, boolean isFirst) {
        if (n <= 1) {
            return isFirst ? 1 : 0;
        }
        int ways = 0;
        if (isFirst) {
            ways += countWinningWays(n - 1, false) + countWinningWays(n - 2, false);
        } else {
            ways += countWinningWays(n - 1, true) + countWinningWays(n - 2, true);
        }
        return ways;
    }
}